import numpy as np
import random
import math
pop_size = 100
generations = 100
mutation_rate = 0.1

# node_cpu_capacity = None
# node_mem_capacity = None
# node_disk_capacity = None
    
def random_individual():
    
    # 随机生成一个可行解
    deploy = np.zeros((node_num, ms_types), dtype=int)
    # 先保证每种微服务至少有一个
    # for t in range(ms_types):
    #     n = random.randint(0, node_num - 1)
    #     deploy[n, t] = 1
    # 随机分配剩余
    for n in range(node_num):
        init_num = math.floor(min(
            (node_cpu_capacity // np.max(cpu_cost)),
            (node_mem_capacity // np.max(mem_cost)),
            (node_disk_capacity // np.max(disk_cost))
        ))
        for _ in range(init_num):
            ms_index=random.randint(0, ms_types-1)
            deploy[n, ms_index]+=1
    return deploy

def is_valid(deploy):
    # 检查每个节点资源约束
    for n in range(node_num):
        cpu = np.sum(deploy[n] * cpu_cost)
        mem = np.sum(deploy[n] * mem_cost)
        disk = np.sum(deploy[n] * disk_cost)
        if cpu > node_cpu_capacity or mem > node_mem_capacity or disk > node_disk_capacity:
            return False
    # 每种微服务至少有一个
    # if np.any(np.sum(deploy, axis=0) < 1):
    #     return False
    return True

def fitness(deploy):
    # 1. 总部署数量（主目标，归一化）
    total = np.sum(deploy)
    max_total = node_num * np.max([
        node_cpu_capacity // cpu_cost,
        node_mem_capacity // mem_cost,
        node_disk_capacity // disk_cost
    ], axis=0).sum()
    total_score = total 

    # 2. 跨节点权重（越小越好，归一化为负分）
    cross_weight = 0
    for i in range(node_num):
        for j in range(i+1, node_num):
            cross_weight += np.sum(weight_matrix * np.outer(deploy[i], deploy[j]))
    # 归一化
    max_cross_weight = (np.sum(weight_matrix) * (total // ms_types) ** 2 * node_num * (node_num-1) / 2)
    cross_weight_score = 1 - (cross_weight / (max_cross_weight + 1e-6))  # 越大越好

    # 3. 微服务比例（越接近越好，归一化为负分）
    ms_total = np.sum(deploy, axis=0)
    ms_sum = np.sum(ms_total)
    ms_total_ratio = ms_total / ms_sum if ms_sum > 0 else ms_ratio
    ratio_diff = np.sum(np.abs(ms_total_ratio - ms_ratio)) / 2  # 归一化到[0,1]
    ratio_score = 1 - ratio_diff  # 越大越好

    # 4. 分散度（Gini–Simpson index，越大越好）
    dispersion_scores = []
    for t in range(ms_types):
        ms_on_nodes = deploy[:, t]
        total_t = np.sum(ms_on_nodes)
        if total_t == 0:
            dispersion_scores.append(0)
            continue
        p = ms_on_nodes / total_t
        gini_simpson = 1 - np.sum(p ** 2)
        dispersion_scores.append(gini_simpson)
    dispersion_score = np.mean(dispersion_scores)  # 所有类型的平均分散度
    
    # 组合目标（可调权重）
    return total_score +  0.01*cross_weight_score + ratio_score + 0.01*dispersion_score

def crossover(parent1, parent2):
    # 单点交叉
    point = random.randint(1, node_num - 1)
    child = np.vstack((parent1[:point], parent2[point:]))
    return child

def mutate(deploy):
    ms_types = len(cpu_cost)
    # 随机节点、微服务类型，增减数量
    n = random.randint(0, node_num - 1)
    t = random.randint(0, ms_types - 1)
    if random.random() < 0.5 and deploy[n, t] > 0:
        deploy[n, t] -= 1
    else:
        deploy[n, t] += 1
    return deploy

def GA_algorithm(weight_matrix_t, cpu_cost_t, mem_cost_t, disk_cost_t, ms_ratio_t, node_num_t, resource_percent=1):
    global weight_matrix, cpu_cost, mem_cost, disk_cost, ms_ratio, node_num, ms_types, node_cpu_capacity, node_mem_capacity, node_disk_capacity
    weight_matrix=weight_matrix_t
    cpu_cost=cpu_cost_t
    mem_cost=mem_cost_t
    disk_cost=disk_cost_t
    ms_ratio=ms_ratio_t
    node_num=node_num_t
    ms_types = len(cpu_cost)
    
    node_cpu_capacity = 100*resource_percent
    node_mem_capacity = 100*resource_percent
    node_disk_capacity = 100*resource_percent
    
    population = []
    while len(population) < pop_size:
        print(len(population))
        ind = random_individual()
        if is_valid(ind):
            population.append(ind)
    print("pop init end!(GA)")
    for gen in range(generations):
        fitnesses = [fitness(ind) for ind in population]
        # 选择
        selected = [population[i] for i in np.argsort(fitnesses)[-pop_size//2:]]
        # 生成新一代
        new_population = []
        while len(new_population) < pop_size:
            p1, p2 = random.sample(selected, 2)
            child = crossover(p1, p2)
            if random.random() < mutation_rate:
                child = mutate(child)
            if is_valid(child):
                new_population.append(child)
        population = new_population
        if (gen+1) % 10 == 0:
            print(f"Generation {gen+1}, best fitness: {max(fitnesses):.2f}")
    # 返回最优解
    best_idx = np.argmax([fitness(ind) for ind in population])
    best = population[best_idx]
    print("Best deployment:\n", best)
    print("Total deployed:", np.sum(best))
    print("Per type:", np.sum(best, axis=0))
    return best

if __name__ == "__main__":
    # 微服务权重矩阵
    weight_matrix_t = np.array([[2, 3], [6, 7]])
    cpu_cost_t = np.array([2, 5])
    mem_cost_t = np.array([3, 4])
    disk_cost_t = np.array([5, 6])
    ms_ratio_t = np.array([0.8, 0.2])

    node_num_t = 10
    
    
    GA_algorithm(weight_matrix_t, cpu_cost_t, mem_cost_t, disk_cost_t, ms_ratio_t, node_num_t)












